1179C - Serge and Dining Room - CodeForces Solution

// Problem: https://codeforces.com/contest/1179/problem/C

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using lint = long long int;
using str = string;
using db = double;
using ld = long double;
template <typename T> using V = vector<T>;
template <typename A, typename B> using PR = pair<A, B>;
template <typename A, typename B, typename C> using TP = tuple<A, B, C>;
template <typename... Args> using PQ = std::priority_queue<Args...>;

namespace ReadandPrint {
    template <typename T> void read(T &n) {cin >> n;}
    template <typename F, typename S> void read(pair<F, S> &p) {read(p.first); read(p.second);}
    template <typename T, typename... Args> void read(T &n, Args&... args) {read(n); read(args...);}

    template <typename T> void print(T n) {cout << n;}
    template <typename T, typename... Args> void print(T n, Args... args) {print(n); print(args...);}

    template <typename T> void dbgprint(T n) {cerr << n;}
    template <typename T, typename... Args> void dbgprint(T n, Args... args) {dbgprint(n); dbgprint(args...);}
}

#define all(x) begin(x), end(x)
#define forn0(i, n) for (int i = 0; i < (n); i++)
#define forn1(i, n) for (int i = 1; i <= (n); i++)
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define repe(i, a, b) for (int i = (a); i <= (b); i++)
#define trav(a, b) for (auto &a : b)
#define len(a) a.length()
#define sz(a) a.size()
#define pb push_back
#define ff first
#define ss second 
#define mp make_pair
#define dbgvar(a) cout << "(Line " << __LINE__ << ")\t" << #a << " = " << a << "\n"
#define END_VOID return
#define END_MAIN return 0

namespace IO {
    void FASTIO() {
        ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr), cin.exceptions(cin.failbit);
    }

    void setFile(const string namein = "", const string nameout = "", const bool b = false, const bool b1 = true) {
        if (b) {
            if (namein.size()) freopen(namein.c_str(), "r", stdin);
            if (nameout.size()) freopen(nameout.c_str(), "w", stdout);
            return;
        } else {
            if (!b1) return;
            cerr << "WARNING: No file is set. Set file before submitting\n";
            cerr << "---------------------------------------------------\n\n";
            return;
        }
    }

    using clock = chrono::steady_clock;

    clock::time_point timeNow() {
        return clock::now();
    }

    void printTime(clock::time_point start, clock::time_point end, bool b = true) {
        if (!b) return;
        cerr << "\nTime of program is " <<chrono::duration <double, milli> (end - start).count() << " ms" << "\n";
        cerr << "REMEMBER TO COMMENT THIS STATEMENT BEFORE SUBMITTING\n\n";
        cerr << "----------------------------------------------------";
        return;
    }
}

//===============================================================================================================
using namespace ReadandPrint;
using namespace IO;

#define int ll

struct info {int sum, mx;};

class SegTree {
    private:
        int n;
        V<info> t;
        int size;
    public:
        SegTree(int N) {
            n = N;
            size = 1;
            while (size < n) size *= 2;
            t.resize(2 * size);
        }

        void pull(int x) {
            t[x].sum = t[2 * x].sum + t[2 * x + 1].sum;
            t[x].mx = max(t[2 * x + 1].mx, t[2 * x + 1].sum + t[2 * x].mx);
        }

        void update(int x, int l, int r, int p, int v) {
            if (l == r) {
                t[x].sum += v;
                t[x].mx = t[x].sum;
                return;
            }
            int m = (l + r) / 2;
            if (p <= m) update(2 * x, l, m, p, v);
            else update(2 * x + 1, m + 1, r, p, v);
            pull(x);
        }

        void update(int p, int v) {
            update(1, 0, n - 1, p, v);
        }

        int query(int x, int l, int r, int suf) {
            if (t[x].mx <= 0) {
                return -1;
            }
            if (l == r) {
                return l;
            }
            int m = (l + r) / 2;
            if (t[2 * x + 1].mx + suf > 0) {
                return query(2 * x + 1, m + 1, r, suf);
            } else {
                return query(2 * x, l, m, suf + t[2 * x + 1].sum);
            }
        }

        int query() {
            return query(1, 0, n - 1, 0);
        }
};

void solve() {
    int n, m; read(n, m);
    auto start = timeNow();
    SegTree ST(1000005);
    V<int> a(n), b(m);

    forn0(i, n) {
        read(a[i]);
        ST.update(a[i], 1);
    }

    forn0(i, m) {
        read(b[i]);
        ST.update(b[i], -1);
    }

    int q; read(q);
    while (q--) {
        int op; read(op);
        if (op == 1) {
            int i, x; read(i, x);
            --i;
            ST.update(a[i], -1);
            ST.update(a[i] = x, 1);
        } else {
            int i, x; read(i, x);
            --i;
            ST.update(b[i], 1);
            ST.update(b[i] = x, -1);
        }

        print(ST.query(), "\n");
    }

    auto end = timeNow();
    printTime(start, end, false);
}

signed main() {
    FASTIO();
    setFile("", "", false, false);

    solve();

    END_MAIN;
}